# -*- coding:utf-8 -*-
"""
Created on May 2, 2011

@author: bob
"""
from random import randint, random
from multi_robot_problem import MultiRobotState

class ProblemGenerator:
    
    EASY = 0
    MED  = 1
    HARD = 2
    NARWHALS = 3 #as near-walls
    
    DIR_VERT = 1
    DIR_HORI = 0
    
    OBS_WALL = 0
    OBS_COMPLEX = 1
    
    def __init__(self, height, width, minRobs, maxRobs, diff, minPiles, 
                 maxPiles, minObs, maxObs, minWallLength, maxWallLength):
        self.h, self.w = height, width
        self.minR, self.maxR = minRobs, maxRobs
        self.minP, self.maxP = minPiles, maxPiles
        self.minObs, self.maxObs = minObs, maxObs
        self.minWallLength = minWallLength
        self.maxWallLength = maxWallLength
        self.diff = diff
        self.dirProbability = 0.5
        
        self.numRobs = randint(minRobs, maxRobs)
        self.numPiles = randint(minPiles,maxPiles)
        self.nWalls = randint(minObs, maxObs)
        self.freePoints = []
        for i in range(0,width):
            for j in range(0, height):
                self.freePoints.append((i,j))
        self.takenPoints = {}
        self.obstacles = set()
        

    def trollProblem(self):
        self.reInit()
        robots = []
        for i in range(0,self.numRobs):
            robotLoc = self.freePoints[randint(0, len(self.freePoints)-1)]
            robots.append(robotLoc)
            self.freePoints.remove(robotLoc)
            self.takenPoints[robotLoc] = 1
        robots = tuple(robots)
#        print "robots:", robots
#        print "free:", self.freePoints
        
        piles = []
        for i in range(0,self.numPiles):
            pileLoc = self.freePoints[randint(0, len(self.freePoints))-1]
            piles.append(pileLoc)
            self.freePoints.remove(pileLoc)
            self.takenPoints[pileLoc] = 1
        
#        print piles
#       make only walls and make sure no walls touch 
        if self.diff == self.MED:
            for i in range (0, self.nWalls):
                wall, dir = self.generateObstacle(self.OBS_WALL)
                self.surroundWithFreePoints(wall)
    
        if self.diff == self.HARD:
            for i in range (0, self.nWalls):
                obs = self.generateObstacle(self.OBS_COMPLEX)
#        return None
        if self.diff == self.NARWHALS:
            def adjacentPoints(p):
                points = []
                for delx, dely in [(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]:
                    xnew, ynew = p[0]+delx, p[1]+dely
                    points.append((xnew,ynew))
                return points
            
            self.dirProbability = 0.85
            for i in range (0, self.nWalls):
                p = self.getRandomStartPoint(piles)
                adj = adjacentPoints(p)
                for adjPoint in adj:
                    if adjPoint in self.freePoints:                    
                        self.generateObstacle(self.OBS_WALL, adjPoint)
                    break;
            self.dirProbability = 0.5
        piles = frozenset(piles)    
        state = MultiRobotState(self.w,self.h, robots, piles, frozenset(self.obstacles))        
        if self.checkForSolution(state) == False:
            return self.trollProblem()
        return state    
    
    def generateObstacle(self, type = OBS_WALL, startAt = None):
        if startAt is None:
            startAt = self.getRandomStartPoint(self.freePoints)
            if startAt == None:
                return
        if type == self.OBS_WALL:
            if random() < self.dirProbability:
                dir = self.DIR_VERT
            else:
                dir = self.DIR_HORI
            return self.populateObsPoints(startAt, dir), dir
        else:
            w1, dir1 = self.generateObstacle(self.OBS_WALL, startAt)    
            next = randint(0,1)
            if next == 0:
                return set(w1),dir1
#           since dir is 1 or 0, 1- dir gives the other one 
            dir = 1 - dir1
            startAt = self.getRandomStartPoint(w1)
            w2, dir2 = self.populateObsPoints(startAt, dir), dir
            next = randint(0,1)
            if next == 0:
                return set(w2).union(set(w1)),dir2
            toConcatTo = randint(0,1)
            if toConcatTo == 0:
                w, dir = w1,dir1
            else:
                w, dir = w2, dir2
            dir = 1 - dir1
            startAt = self.getRandomStartPoint(w)
            w3 = self.populateObsPoints(startAt, dir)
            return set(w3).union(set(w2).union(set(w1))),dir
        
    def populateObsPoints(self, startAt, dir):
        length = randint(self.minWallLength, self.maxWallLength)
        obsPoints = []
        for i in range(0, length):
            if dir == 0:
                point = (startAt[0]+i, startAt[1])
            else:
                point = (startAt[0], startAt[1]+i)    
            if point in self.freePoints:
                obsPoints.append(point)
                self.obstacles.add(point)
                self.freePoints.remove(point)    
                self.takenPoints[point] = 1
            else:
                break
        if len(obsPoints) == 0:
            obsPoints.append(startAt)
        return obsPoints
        
    def surroundWithFreePoints(self, w):
        for x,y in w:
            for delx, dely in [(1,0),(-1,0),(0,1),(0,-1)]:
                xnew, ynew = x+delx, y+dely
                if (xnew,ynew) in self.freePoints:
                    self.freePoints.remove((xnew,ynew))
                    self.takenPoints[(xnew,ynew)] = 1
        
    def getRandomStartPoint(self, col):
        if len(col) == 0:
            return None
        if len(col) == 1:
            return col[0]
        return col[randint(0, len(col)-1)]
        
    def checkForSolution(self, pState):
        reachable = set()
        closure = set()
        for r in pState.robots:
            closure.add(r)
        while len(reachable ^ closure) > 0:
            reachable = closure.copy()
            for x,y in reachable:
                for delx, dely in [(1,0),(-1,0),(0,1),(0,-1)]:
                    xnew, ynew = x+delx, y+dely
                    if xnew < 0 or xnew >= pState.width or ynew < 0 or ynew > pState.height:
                        continue
                    if (xnew, ynew) in pState.obstacle_locations:
                        continue
                    closure.add((xnew, ynew))
        for p in pState.dirt_locations:
            if not p in reachable:
                return False
        return True    
        
    def reInit(self):
        self.numRobs = randint(self.minR, self.maxR)
        self.numPiles = randint(self.minP,self.maxP)
        self.nWalls = randint(self.minObs, self.maxObs)
        self.freePoints = []
        for i in range(0,self.w):
            for j in range(0, self.h):
                self.freePoints.append((i,j))
        self.takenPoints = {}
        self.obstacles = set()
        